﻿namespace Leetcode.N0139;

public class Solution
{
    public bool WordBreak(string s, IList<string> wordDict)
    {
        var flg = new bool[s.Length + 1];
        var words = new HashSet<string>();
        foreach (var item in wordDict)
        {
            words.Add(item);
        }

        flg[0] = true;
        for (var i = 1; i <= s.Length; i++)
        {
            for (var j = 0; j < i; j++)
            {
                if (flg[j] && words.Contains(s.Substring(j, i - j)))
                {
                    flg[i] = true;
                    break;
                }
            }
        }
        return flg[s.Length];
    }
}
